package com.south.base.test.arithmetic.arrays;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * @author Administrator
 * @date 2020/4/24 15:04
 */
public class FindNum {
    /**
     * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     */
    @Test
    public void test() {
        Assert.assertEquals(5, findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
        Assert.assertEquals(4, findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
        Assert.assertEquals(5, findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 2));
        Assert.assertEquals(6, findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 1));
        Assert.assertEquals(-1, findKthLargest(new int[]{-1, -1}, 2));
        Assert.assertEquals(-1, findKthLargest2(new int[]{-1, -1}, 2));
        Assert.assertEquals(-1, findKthLargest3(new int[]{-1, -1}, 2));
    }

    public int findKthLargest(int[] nums, int k) {
        if (k == 0 || nums.length == 0) {
            return 0;
        }
        int[] ints = new int[k];
        for (int i = 1; i < ints.length; i++) {
            ints[i] = Integer.MIN_VALUE;
        }
        ints[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
//            int tmp = nums[i];
            for (int j = 0; j < ints.length; j++) {
                if (nums[i] > ints[j]) {
                    System.arraycopy(ints, j, ints, j + 1, ints.length - j - 1);
                    ints[j] = nums[i];
                    break;
                }
            }
        }
        return ints[ints.length - 1];
    }

    /**
     * 最大堆
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest2(int[] nums, int k) {
        // init heap 'the smallest element first'
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n));

        // keep k largest elements in the heap
        for (int n : nums) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }

        // output
        return heap.poll();
    }

    /**
     * 快速选择
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest3(int[] nums, int k) {
        int size = nums.length;
        // kth largest is (N - k)th smallest
        return quickselect(nums, 0, size - 1, size - k);
    }

    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }


    public int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivot = nums[pivotIndex];
        // 1. move pivot to end
        swap(nums, pivotIndex, right);
        int storeIndex = left;

        // 2. move all smaller elements to the left
        for (int i = left; i <= right; i++) {
            if (nums[i] < pivot) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }

        // 3. move pivot to its final place
        swap(nums, storeIndex, right);

        return storeIndex;
    }

    public int quickselect(int[] nums, int left, int right, int k_smallest) {
    /*
    Returns the k-th smallest element of list within left..right.
    */

        if (left == right) // If the list contains only one element,
            return nums[left];  // return that element

        // select a random pivotIndex
        Random random_num = new Random();
        int pivotIndex = left + random_num.nextInt(right - left);

        pivotIndex = partition(nums, left, right, pivotIndex);

        // the pivot is on (N - k)th smallest position
        if (k_smallest == pivotIndex)
            return nums[k_smallest];
            // go left side
        else if (k_smallest < pivotIndex)
            return quickselect(nums, left, pivotIndex - 1, k_smallest);
        // go right side
        return quickselect(nums, pivotIndex + 1, right, k_smallest);
    }

    /**
     * 至少是其他数字两倍的最大数
     * 在一个给定的数组nums中，总是存在一个最大元素 。
     * 查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
     * 如果是，则返回最大元素的索引，否则返回-1。
     */
    @Test
    public void dominantIndex() {
        Assert.assertEquals(1, dominantIndex(new int[]{3, 6, 1, 0}));
        Assert.assertEquals(-1, dominantIndex(new int[]{3, 6, 1, 0, 5}));
        Assert.assertEquals(0, dominantIndex(new int[]{1, 0}));
        Assert.assertEquals(0, dominantIndex(new int[]{1}));
    }

    public int dominantIndex(int[] nums) {
        int res = -1;
        if (nums.length < 1) {
            return res;
        }
        if (nums.length == 1) {
            return 0;
        }
        int indexMax = 0, indexPre = -1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[indexMax]) {
                int tmp = indexMax;
                indexMax = i;
                indexPre = tmp;
            } else if (indexPre < 0 || nums[i] > nums[indexPre]) {
                indexPre = i;
            }
        }
        res = nums[indexMax] / 2 >= nums[indexPre] ? indexMax : -1;
        return res;
    }

    /**
     * 有序矩阵中第K小的元素
     * 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
     * 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
     */
    @Test
    public void kthSmallest() {
        Assert.assertEquals(13, kthSmallest(new int[][]{{1, 5, 9}, {10, 11, 13}, {12, 13, 15}}, 8));
    }

    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(int[][] matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }

    public int kthSmallest2(int[][] matrix, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());

        for (int[] nums : matrix) {
            for (int n : nums) {
                heap.add(n);
                if (heap.size() > k)
                    heap.poll();
            }
        }

        // output
        return heap.poll();
    }

    /**
     * 数组中数字出现的次数
     * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。
     * 请写程序找出这两个只出现一次的数字
     */
    @Test
    public void singleNumbers() {
        Assert.assertArrayEquals(new int[]{1, 6}, singleNumbers(new int[]{4, 1, 4, 6}));
        Assert.assertArrayEquals(new int[]{2, 10}, singleNumbers(new int[]{1, 2, 10, 4, 1, 4, 3, 3}));
    }

    public int[] singleNumbers(int[] nums) {
        int xorSum = 0;
        int[] ret = new int[2];
        for (int x : nums) {
            xorSum ^= x;
        }
        int lowBit = xorSum & (-xorSum);
        for (int x : nums) {
            ret[(x & lowBit) > 0 ? 0 : 1] ^= x;
        }
        Arrays.sort(ret);
        return ret;
    }

    /**
     * 把数组排成最小的数
     * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
     */
    @Test
    public void minNumber() {
        Assert.assertEquals("102", minNumber(new int[]{10, 2}));
        Assert.assertEquals("3033459", minNumber(new int[]{3, 30, 34, 5, 9}));
    }

    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for (String s : strs)
            res.append(s);
        return res.toString();
    }

    /**
     * 缺失的第一个正数
     */
    @Test
    public void firstMissingPositive() {
        Assert.assertEquals(3, firstMissingPositive(new int[]{1, 2, 0}));
        Assert.assertEquals(2, firstMissingPositive(new int[]{3, 4, -1, 1}));
        Assert.assertEquals(2, firstMissingPositive(new int[]{1}));
        Assert.assertEquals(1, firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
    }

    public int firstMissingPositive(int[] nums) {
        if (nums.length == 0) {
            return 1;
        }
        boolean[] tmp = new boolean[nums.length];
        for (int num : nums) {
            if (num > 0 && num <= nums.length) {
                tmp[num - 1] = true;
            }
        }
        for (int i = 0; i < tmp.length; i++) {
            if (!tmp[i]) {
                return i + 1;
            }
        }
        return tmp.length + 1;
    }


    /**
     * 在排序数组中查找元素的第一个和最后一个位置
     */
    @Test
    public void searchRange() {
        Assert.assertArrayEquals(new int[]{3, 4}, searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8));
        Assert.assertArrayEquals(new int[]{-1, -1}, searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6));
        Assert.assertArrayEquals(new int[]{-1, -1}, searchRange(new int[]{1}, 0));
    }

    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{0, nums.length - 1};
        int tmp = res[1];
        while (res[0] <= res[1]) {
            int mid = (res[0] + res[1]) / 2;
            if (nums[mid] < target) {
                res[0] = mid + 1;
            } else if (nums[mid] > target) {
                res[1] = mid - 1;
                tmp = res[1];
            } else if (nums[mid] == target) {
                res[1] = mid - 1;
            }
        }
        if (res[0] >= nums.length || nums[res[0]] != target) {
            return new int[]{-1, -1};
        }
        res[1] = tmp;
        tmp = res[0];
        while (res[0] <= res[1]) {
            int mid = (res[0] + res[1]) / 2;
            if (nums[mid] <= target) {
                res[0] = mid + 1;
            } else if (nums[mid] > target) {
                res[1] = mid - 1;
            }
        }
        res[0] = tmp;
        return res;
    }

    /**
     * 被围绕的区域
     * 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
     * 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     */
    private static final char X = 'X';
    private static final char O = 'O';

    @Test
    public void findSurrounded() {
        char[][] in = new char[][]{
                {X, X, X, X},
                {X, O, O, X},
                {X, X, O, X},
                {X, O, X, X}};
        findSurrounded(in);
        Assert.assertArrayEquals(new char[][]{
                {X, X, X, X},
                {X, X, X, X},
                {X, X, X, X},
                {X, O, X, X}}, in);
        in = new char[][]{
                {X, X, X, X},
                {X, O, O, X},
                {X, X, O, X},
                {X, O, X, X}};
        findSurrounded2(in);
        Assert.assertArrayEquals(new char[][]{
                {X, X, X, X},
                {X, X, X, X},
                {X, X, X, X},
                {X, O, X, X}}, in);
    }

    public void findSurrounded(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (X == board[i][j] || visited[i][j]) {
                    continue;
                }
                findSurrounded(i, j, board, visited);
            }
        }
    }

    public void findSurrounded(int i, int j, char[][] board, boolean[][] visited) {
        int[][] dirs = new int[][]{
                // 右移一位
                {1, 0},
                // 左移一位
                {-1, 0},
                // 上移一位
                {0, 1},
                // 下移一位
                {0, -1}
        };
        Queue<int[]> queue = new LinkedList<>(), tmp = new LinkedList<>();
        visited[i][j] = true;
        boolean f = isBound(i, j, board.length, board[0].length);
        queue.add(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] ints = queue.poll();
            if (ints == null) {
                break;
            }
            tmp.add(ints);
            for (int[] dir : dirs) {
                int nx = ints[0] + dir[0], ny = ints[1] + dir[1];
                if (inBound(nx, ny, board.length, board[0].length) && board[nx][ny] == O && !visited[nx][ny]) {
                    if (isBound(nx, ny, board.length, board[0].length)) {
                        f = true;
                    }
                    queue.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        if (!f) {
            boardX(tmp, board);
        }
    }

    public void boardX(Queue<int[]> queue, char[][] board) {
        while (!queue.isEmpty()) {
            int[] ints = queue.poll();
            if (ints == null) {
                break;
            }
            board[ints[0]][ints[1]] = X;
        }
    }

    public boolean inBound(int x, int y, int n, int m) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }

    public boolean isBound(int x, int y, int n, int m) {
        return x == 0 || x == n - 1 || y == 0 || y == m - 1;
    }

    public void findSurrounded2(char[][] board) {
        int rows = board.length;
        if (rows == 0) {
            return;
        }
        int cols = board[0].length;
        for (int i = 0; i < cols; i++) {
            if (board[0][i] == 'O') {
                findSurrounded2(0, i, board);
            }
            if (board[rows - 1][i] == 'O') {
                findSurrounded2(rows - 1, i, board);
            }
        }
        for (int i = 1; i < rows - 1; i++) {
            if (board[i][0] == 'O') {
                findSurrounded2(i, 0, board);
            }
            if (board[i][cols - 1] == 'O') {
                findSurrounded2(i, cols - 1, board);
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                board[i][j] = board[i][j] == '*' ? 'O' : 'X';
            }
        }
    }

    public void findSurrounded2(int i, int j, char[][] board) {
        if (i < 0 || j < 0 || i == board.length || j == board[0].length) {
            return;
        }
        if (board[i][j] == '*') {
            return;
        }
        if (board[i][j] == 'O') {
            board[i][j] = '*';
            findSurrounded2(i + 1, j, board);
            findSurrounded2(i - 1, j, board);
            findSurrounded2(i, j + 1, board);
            findSurrounded2(i, j - 1, board);
        }
    }

    /**
     * 扫雷游戏
     * 给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
     * 现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
     * 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
     * 如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。
     * 如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
     * 如果在此次点击中，若无更多方块可被揭露，则返回面板。
     */
    @Test
    public void updateBoard() {
        Assert.assertArrayEquals(new char[][]{
                {'B', '1', 'E', '1', 'B'},
                {'B', '1', 'M', '1', 'B'},
                {'B', '1', '1', '1', 'B'},
                {'B', 'B', 'B', 'B', 'B'}
        }, updateBoard(new char[][]{
                {'E', 'E', 'E', 'E', 'E'},
                {'E', 'E', 'M', 'E', 'E'},
                {'E', 'E', 'E', 'E', 'E'},
                {'E', 'E', 'E', 'E', 'E'}
        }, new int[]{3, 0}));
        Assert.assertArrayEquals(new char[][]{
                {'B', '1', 'E', '1', 'B'},
                {'B', '1', 'X', '1', 'B'},
                {'B', '1', '1', '1', 'B'},
                {'B', 'B', 'B', 'B', 'B'}
        }, updateBoard(new char[][]{
                {'B', '1', 'E', '1', 'B'},
                {'B', '1', 'M', '1', 'B'},
                {'B', '1', '1', '1', 'B'},
                {'B', 'B', 'B', 'B', 'B'}
        }, new int[]{1, 2}));
    }

    public char[][] updateBoard(char[][] board, int[] click) {
        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            // 规则 1
            board[x][y] = 'X';
        } else {
            dfs(board, x, y);
        }
        return board;
    }

    public void dfs(char[][] board, int x, int y) {
        int[] dirX = {0, 1, 0, -1, 1, 1, -1, -1};
        int[] dirY = {1, 0, -1, 0, 1, -1, 1, -1};
        int cnt = 0;
        for (int i = 0; i < 8; ++i) {
            int tx = x + dirX[i];
            int ty = y + dirY[i];
            if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length) {
                continue;
            }
            // 不用判断 M，因为如果有 M 的话游戏已经结束了
            if (board[tx][ty] == 'M') {
                ++cnt;
            }
        }
        if (cnt > 0) {
            // 规则 3
            board[x][y] = (char) (cnt + '0');
        } else {
            // 规则 2
            board[x][y] = 'B';
            for (int i = 0; i < 8; ++i) {
                int tx = x + dirX[i];
                int ty = y + dirY[i];
                // 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了
                if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length || board[tx][ty] != 'E') {
                    continue;
                }
                dfs(board, tx, ty);
            }
        }
    }
}
